1. Technical Field
The present invention is directed generally toward a method and apparatus for providing hardware-controlled data integrity for data that does not have a fixed block length.
2. Description of the Related Art
When writing to a device such as a tape, it can be necessary to provide buffering between a bus and an actual device to smooth out the bursts from the bus into a steady flow onto the tape. This can be handled by a double data rate (DDR) memory device, which allows data to be written and read from the same memory at different rates. Off-the-shelf DDR memory devices are available in a variety of sizes that vary both in the number of bits that can be accessed in parallel and in the number of bits that can be stored. In order to support a high data rate, it is desirable to have the capability to handle a large number of bits in parallel, e.g., 32 bits.
As in all forms of data transmission and storage, whether temporary or permanent, it is necessary to ensure the integrity of the data during the short time that it resides on the DDR memory device. This data integrity can be ensured by on of several means.
One exemplary means is by the addition of a single parity bit to a fixed-size set of bits, with the value of the parity bit determined by the values of the set of bits. To add an odd parity to a string of n bits, a single bit can be added to ensure that the number of ones in the string is odd. For example, to transmit the four-bit string 1100, one adds a 1 parity bit at the end and transmits the string 11001. If an error occurs, e.g. the string is received as 11011, the receiving device determines that the total number of ones is even, so it is clear that an error has occurred. However, using the single parity bit, it is impossible to determine which bit is in error, so the data must be resent.
Error correction codes (ECCs) carry this one step farther, by providing enough information that the error can be pinpointed by location and corrected, as long as there are only a limited number of errors in the group of bits. The downside of an ECC is that it adds a number of bits to the data stream. For example, using the Hamming code, a common error correction code, three parity bits must be added to four bits of data to ensure that the location of an error can be pinpointed. Luckily, the ratio of data to parity does not remain quite this high, although it is still significant: a four-bit Hamming code will protect eight bits of data; a five-bit code will protect twenty-four bits of data; a six-bit code will protect twenty-eight bits of data, and a 7-bit code will protect thirty-two bits of data. Due to the structure of this code, it can correct a single error or detect several errors, but cannot correct a large number of errors. Other EEC codes will correct n errors and detect n+m errors, with n and m determined by the code formula and number of bits protected.
A cyclical redundancy code (CRC) is another technique, used to protect blocks of data, called frames. For each frame, an n-bit sequence, called a Frame Check Sequence (FCS) is added to the frame. The FCS is calculated such that the new frame, with FCS appended to the original frame, is exactly divisible by a polynomial. When the data is used, the new frame is divided by the same polynomial; if the remainder is not zero, there is an error in the frame.
In order to provide data protection during temporary storage in a DDR memory device, as described above, any of these approaches can be used, if one is willing to deal with the drawbacks. For example, when using a Hamming code with a high data-rate, it becomes necessary to provide either two 32-bit or three 16-bit DDR memory devices in order to pass through both the data and the added code.
In the same situation, a cyclical redundancy code that works on frames would require only one 32-bit DDR memory device. Typically, in a DDR memory device, the application uses a single frame check sequence (FCS) for a large block, such as an entire SCSI command transfer. However, when working with data that is not in fixed lengths, the FCS must be generated and checked by software, a much slower process. With the slower capabilities of software, it is tempting to generate an FCS for as large a block as possible, although this degrades the protection capabilities.
It would be desirable to provide a method of protecting data that is not organized in fixed-length blocks, where the method would provide a high degree of reliability using only one DDR memory device and without resorting to a software-controlled CRC.